1. Technical Field of the Invention
The present invention relates to compilers and, more particularly, to compilers that perform invalidation profiling for data speculation.
2. Background Art
A compiler is a program that reads a source program written in a source language and translates it into a target program in a target language. For example, a compiler may translate a high level source program (such as C++) into compiled code that can be understood by a processor, such as a microprocessor.
Many compilers include three stages: (1) a "front end" in which the source program is translated into intermediate representations; (2) a "middle end" in which machine independent optimizations are made; and (3) a "back end" in which machine dependent optimizations are made and code is generated. Optimizations can significantly improve running time and/or space requirements of the target program. However, "optimized" code is not necessarily optimal under any mathematical measure.
There have been attempts to find invalidation rates by comparing the addresses of load-store pairs. This approach may be referred to as a "pair-wise" approach. The pair-wise approach collects conflict rate as the probability that a load (L) and a store (S) access the same memory location. The pair-wise conflict rate is denoted PCR (L,S). Although pair-wise conflict rate has other uses, such as disambiguation in dependence analysis, it has several serious problems for directing data speculation. A fundamental limitation with the pair-wise approach is that PCR (L, S) is not schedule-region sensitive.
Data speculation may be expensive because recovery can take many CPU cycles. A study of data speculation, Gallagher et al., "Dynamic Memory Disambiguation Using the Memory Conflict Buffer," ACM SIGPLAN Notices, Nov. 1, 1994, v29 n11, p. 183, considered only register pressure as the cost of data speculation. The recovery cost was ignored by treating the number of cycles in a recover as equaling the number of cycles in a regular load. For many situations, this is not a realistic assumption.
Accordingly, there is a need for a compiler that performs accurate invalidation profiling for data speculation.